A video output from a digital video camera is generally a sequence of frames, each frame being a snapshot generated by the camera's row-column array of what is often millions of optical sensors. Each frame is a time sample of the impinging image and, therefore, the rate of the frames can be associated with the highest rate of motion the user desires to capture. For example, a frame rate of 15 to 30 frames per second can capture the fastest motion perceptible to the unaided human eye. Higher frame rates, for example in excess of a million frames per second, can be used for capture of high speed motion, e.g., a hummingbird's wing motion or a ballistic event.
Even at lower frame rates, though, if no processing is performed on the data generated by the optical sensors to remove what can be termed unnecessary information, the amount of data required to communicate and store the image can be problematic. Examples of unnecessary data include more image detail than needed, or data that carries little actual information, e.g., adds little or nothing to what has already been carried in a preceding frame. The latter type of information can be termed “inter-frame” redundancy. One example can be a video camera imaging a person running against an unchanging backdrop. In such an image, an unfiltered sequence of frames would carry significant amounts of unneeded information, because in fact the only change from frame to frame may be the position of the man.
Various algorithms are known that exploit this redundancy, for example, by sending only intermittent frames with a complete or substantially complete content, and sending the succeeding or intervening “frames” as only the changes, or delta, from the previous frame. The change or delta that is sent can include a displacement of one or more objects, and such displacements can be represented with one or more motion vectors.
Motion vectors in accordance with various video-encoding standards, for example, H.263, H.264, MPEG-2, and MPEG-4, can be generated with a sub-pixel resolution, such as half-pixel and/or quarter-pixel resolution. Since sub-pixel resolution is greater than the original image, motion vectors with sub-pixel resolution can be estimated by interpolating between original pixels, and further interpolating between interpolated pixels. One well-known problem associated with estimating, or interpolating sub-pixels is computational complexity. A reduction of the computational complexity associated with the estimation of motion vectors with sub-pixel resolution has been long known as desirable.